"""
102. 二叉树的层序遍历
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。



示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]


提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
"""
from typing import Optional, List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def levelOrder(self, root:  Optional[TreeNode]) -> List[List[int]]:
        """
        广度优先遍历?
        :param root:
        :return:
        """

        def dfs(nodes: List[TreeNode], result: List[List[int]]) -> List[List[int]]:
            if not nodes:
                #没有元素了
                return result
            #下一层的节点，可以理解为是一个队列，先进的后续会先遍历
            nextNodesList = []
            #当前节点的值
            curNums = []
            for node in nodes:
                curNums.append(node.val)
                if node.left:
                    nextNodesList.append(node.left)
                if node.right:
                    nextNodesList.append(node.right)
            result.append(curNums)
            return dfs(nextNodesList,result)
        return dfs([root],[]) if root else []

if __name__ == '__main__':
    solution = Solution()
    # 测试用例 1
    root1 = TreeNode(3)
    root1.left = TreeNode(9)
    root1.right = TreeNode(20)
    root1.right.left = TreeNode(15)
    root1.right.right = TreeNode(7)
    result1 = solution.levelOrder(root1)
    print(f"测试用例 1: {result1}")  # 预期输出: [[3],[9,20],[15,7]]

    # 测试用例 2
    root2 = TreeNode(1)
    result2 = solution.levelOrder(root2)
    print(f"测试用例 2: {result2}")  # 预期输出: [[1]]

    # 测试用例 3
    root3 = None
    result3 = solution.levelOrder(root3)
    print(f"测试用例 3: {result3}")  # 预期输出: []

    # list1 = [1,2,3]
    # list1.append(4)
    # print(list1)
    # #删除最后一个
    # print(list1.pop())
    # print(list1)
    # #删除第一个
    # del list1[0]
    # # list1.pop(0)
    # # list1 = list1[1:]
    # print(list1)
